<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>LC 410. Split Array Largest Sum</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="lc-410-split-array-largest-sum">LC 410. Split Array Largest Sum</h1>
<ul>
<li><a href="https://leetcode.com/problems/split-array-largest-sum/">https://leetcode.com/problems/split-array-largest-sum/</a></li>
</ul>
<p>Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.</p>
<p>Write an algorithm to minimize the largest sum among these m subarrays.</p>
<pre><code><code><div>Example 1:
Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Example 2:
Input: nums = [1,2,3,4,5], m = 2
Output: 9

Example 3:
Input: nums = [1,4,4], m = 3
Output: 4
</div></code></code></pre>
<p>本题暴力解法就是遍历所有的m分组可能，找到min(max_sub_sum).  今天看了labuladong的微信文章，本地要反向思维。</p>
<h2 id="二分解法">二分解法</h2>
<p>假设给定了分组后，每个组的最大和sub_sum, 问至少要分配多个组，才能满足要求？  sub_sum的取值范围是 max(nums) ~ sum(nums), 可以在寻求sub_sum的时候，用二分查找。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">splitArray</span><span class="hljs-params">(self, nums: List[int], m: int)</span> -&gt; int:</span>
        left = max(nums)
        right = sum(nums)
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">check</span><span class="hljs-params">(target)</span>:</span>
            count = <span class="hljs-number">0</span>
            t = <span class="hljs-number">0</span>
            <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums:
                <span class="hljs-keyword">if</span> t + num &gt; target:
                    count += <span class="hljs-number">1</span>
                    t = <span class="hljs-number">0</span>
                t += num
            count += <span class="hljs-number">1</span>
            <span class="hljs-keyword">return</span> count
        
        <span class="hljs-keyword">while</span> left &lt; right:
            mid = (left + right) // <span class="hljs-number">2</span>
            r = check(mid)   <span class="hljs-comment"># target 阈值越大，需要分配的组就越少。 target阈值越小，需要分配的组就越多。</span>
            <span class="hljs-keyword">if</span> r == m:       <span class="hljs-comment"># 如果分配的组正好符合要求，我们还是要减少阈值，考虑测试用例 nums=[3,3,3], m=2， 符合条件的答案是6, 当我们阈值是7的时候，我们需要减少阈值，向6靠近。</span>
                right = mid
            <span class="hljs-keyword">elif</span> r &lt; m:       <span class="hljs-comment"># 如果要分配的组少了，我们要减少阈值</span>
                right = mid
            <span class="hljs-keyword">else</span>:              <span class="hljs-comment"># 如果要分配的组多了，我们要增大阈值</span>
                left = mid + <span class="hljs-number">1</span>
                
        <span class="hljs-keyword">return</span> left   
    
        
</div></code></pre>
<h2 id="dp-解法">dp 解法</h2>
<p>Approach #2 Dynamic Programming [Accepted]</p>
<p>The problem satisfies the non-aftereffect property. We can try to use dynamic programming to solve it.</p>
<p>The non-aftereffect property means, once the state of a certain stage is determined, it is not affected by the state in the future. In this problem, if we get the largest subarray sum for splitting nums[0..i] into j parts, this value will not be affected by how we split the remaining part of nums.</p>
<p>To know more about non-aftereffect property, this link may be helpful : <a href="http://www.programering.com/a/MDOzUzMwATM.html">http://www.programering.com/a/MDOzUzMwATM.html</a></p>
<p>Algorithm</p>
<p>Let's define f[i][j] to be the minimum largest subarray sum for splitting nums[0..i] into j parts.</p>
<p>Consider the jth subarray. We can split the array from a smaller index k to i to form it. Thus f[i][j] can be derived from max(f[k][j - 1], nums[k + 1] + ... + nums[i]). For all valid index k, f[i][j] should choose the minimum value of the above formula.</p>
<p>The final answer should be f[n][m], where n is the size of the array.</p>
<p>For corner situations, all the invalid f[i][j] should be assigned with INFINITY, and f[0][0] should be initialized with 0.</p>
<pre><code class="language-java"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">splitArray</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> m)</span> </span>{
        <span class="hljs-keyword">int</span> n = nums.length;
        <span class="hljs-keyword">int</span>[][] f = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[n + <span class="hljs-number">1</span>][m + <span class="hljs-number">1</span>];
        <span class="hljs-keyword">int</span>[] sub = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[n + <span class="hljs-number">1</span>];
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;= n; i++) {
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt;= m; j++) {
                f[i][j] = Integer.MAX_VALUE;
            }
        }
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++) {
            sub[i + <span class="hljs-number">1</span>] = sub[i] + nums[i];
        }
        f[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>] = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;= n; i++) {
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">1</span>; j &lt;= m; j++) {
                <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> k = <span class="hljs-number">0</span>; k &lt; i; k++) {
                    f[i][j] = Math.min(f[i][j], Math.max(f[k][j - <span class="hljs-number">1</span>], sub[i] - sub[k]));
                }
            }
        }
        <span class="hljs-keyword">return</span> f[n][m];        
    }
}
</div></code></pre>

    </body>
    </html>